From e807fc3be0785fb4d4efdb92a0901344c77d2503 Mon Sep 17 00:00:00 2001 From: Benjamin Otte Date: Fri, 17 Jul 2020 01:56:18 +0200 Subject: [PATCH] sortlistmodel: Replace with an array-based model This is the dumbest possible sortmodel using an array: Just grab all the items, put them in the array, qsort() the array. Some benchmarks (setting a new model): 125,000 items - old: 549ms new: 115ms 250,000 items - new: 250ms This performance can not be kept for simple additions and removals though. --- gtk/gtksortlistmodel.c | 246 +++++++++++------------------------------ 1 file changed, 66 insertions(+), 180 deletions(-) diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c index 0e667aefc8..381addd568 100644 --- a/gtk/gtksortlistmodel.c +++ b/gtk/gtksortlistmodel.c @@ -24,6 +24,12 @@ #include "gtkintl.h" #include "gtkprivate.h" +#define GDK_ARRAY_ELEMENT_TYPE GObject * +#define GDK_ARRAY_TYPE_NAME SortArray +#define GDK_ARRAY_NAME sort_array +#define GDK_ARRAY_FREE_FUNC g_object_unref +#include "gdk/gdkarrayimpl.c" + /** * SECTION:gtksortlistmodel * @title: GtkSortListModel @@ -47,8 +53,6 @@ enum { NUM_PROPERTIES }; -typedef struct _GtkSortListEntry GtkSortListEntry; - struct _GtkSortListModel { GObject parent_instance; @@ -56,8 +60,7 @@ struct _GtkSortListModel GListModel *model; GtkSorter *sorter; - GSequence *sorted; /* NULL if known unsorted */ - GSequence *unsorted; /* NULL if known unsorted */ + SortArray items; /* empty if known unsorted */ }; struct _GtkSortListModelClass @@ -65,25 +68,8 @@ struct _GtkSortListModelClass GObjectClass parent_class; }; -struct _GtkSortListEntry -{ - GSequenceIter *sorted_iter; - GSequenceIter *unsorted_iter; - gpointer item; /* holds ref */ -}; - static GParamSpec *properties[NUM_PROPERTIES] = { NULL, }; -static void -gtk_sort_list_entry_free (gpointer data) -{ - GtkSortListEntry *entry = data; - - g_object_unref (entry->item); - - g_slice_free (GtkSortListEntry, entry); -} - static GType gtk_sort_list_model_get_item_type (GListModel *list) { @@ -106,22 +92,17 @@ gtk_sort_list_model_get_item (GListModel *list, guint position) { GtkSortListModel *self = GTK_SORT_LIST_MODEL (list); - GSequenceIter *iter; - GtkSortListEntry *entry; if (self->model == NULL) return NULL; - if (self->unsorted == NULL) + if (sort_array_is_empty (&self->items)) return g_list_model_get_item (self->model, position); - iter = g_sequence_get_iter_at_pos (self->sorted, position); - if (g_sequence_iter_is_end (iter)) + if (position >= sort_array_get_size (&self->items)) return NULL; - entry = g_sequence_get (iter); - - return g_object_ref (entry->item); + return g_object_ref (sort_array_get (&self->items, position)); } static void @@ -136,89 +117,45 @@ G_DEFINE_TYPE_WITH_CODE (GtkSortListModel, gtk_sort_list_model, G_TYPE_OBJECT, G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_sort_list_model_model_init)) static void -gtk_sort_list_model_remove_items (GtkSortListModel *self, - guint position, - guint n_items, - guint *unmodified_start, - guint *unmodified_end) +gtk_sort_list_model_clear_items (GtkSortListModel *self) { - GSequenceIter *unsorted_iter; - guint i, pos, start, end, length_before; - - start = end = length_before = g_sequence_get_length (self->sorted); - unsorted_iter = g_sequence_get_iter_at_pos (self->unsorted, position); - - for (i = 0; i < n_items ; i++) - { - GtkSortListEntry *entry; - GSequenceIter *next; - - next = g_sequence_iter_next (unsorted_iter); + sort_array_clear (&self->items); +} - entry = g_sequence_get (unsorted_iter); - pos = g_sequence_iter_get_position (entry->sorted_iter); - start = MIN (start, pos); - end = MIN (end, length_before - i - 1 - pos); +static void +gtk_sort_list_model_create_items (GtkSortListModel *self) +{ + guint i, n_items; - g_sequence_remove (entry->unsorted_iter); - g_sequence_remove (entry->sorted_iter); + if (self->sorter == NULL || + self->model == NULL || + gtk_sorter_get_order (self->sorter) == GTK_SORTER_ORDER_NONE) + return; - unsorted_iter = next; + n_items = g_list_model_get_n_items (self->model); + sort_array_reserve (&self->items, n_items); + for (i = 0; i < n_items; i++) + { + sort_array_append (&self->items, g_list_model_get_item (self->model, i)); } - - *unmodified_start = start; - *unmodified_end = end; } static int -_sort_func (gconstpointer item1, - gconstpointer item2, - gpointer data) +sort_func (gconstpointer a, + gconstpointer b, + gpointer data) { - GtkSortListEntry *entry1 = (GtkSortListEntry *) item1; - GtkSortListEntry *entry2 = (GtkSortListEntry *) item2; - GtkOrdering result; - - result = gtk_sorter_compare (GTK_SORTER (data), entry1->item, entry2->item); - - if (result == GTK_ORDERING_EQUAL) - result = g_sequence_iter_compare (entry1->unsorted_iter, entry2->unsorted_iter); - - return result; + return gtk_sorter_compare (data, *(GObject **) a, *(GObject **) b); } static void -gtk_sort_list_model_add_items (GtkSortListModel *self, - guint position, - guint n_items, - guint *unmodified_start, - guint *unmodified_end) +gtk_sort_list_model_resort (GtkSortListModel *self) { - GSequenceIter *unsorted_end; - guint i, pos, start, end, length_before; - - unsorted_end = g_sequence_get_iter_at_pos (self->unsorted, position); - start = end = length_before = g_sequence_get_length (self->sorted); - - for (i = 0; i < n_items; i++) - { - GtkSortListEntry *entry = g_slice_new0 (GtkSortListEntry); - - entry->item = g_list_model_get_item (self->model, position + i); - entry->unsorted_iter = g_sequence_insert_before (unsorted_end, entry); - entry->sorted_iter = g_sequence_insert_sorted (self->sorted, entry, _sort_func, self->sorter); - if (unmodified_start != NULL || unmodified_end != NULL) - { - pos = g_sequence_iter_get_position (entry->sorted_iter); - start = MIN (start, pos); - end = MIN (end, length_before + i - pos); - } - } - - if (unmodified_start) - *unmodified_start = start; - if (unmodified_end) - *unmodified_end = end; + g_qsort_with_data (sort_array_get_data (&self->items), + sort_array_get_size (&self->items), + sizeof (GObject *), + sort_func, + self->sorter); } static void @@ -228,24 +165,15 @@ gtk_sort_list_model_items_changed_cb (GListModel *model, guint added, GtkSortListModel *self) { - guint n_items, start, end, start2, end2; - - if (removed == 0 && added == 0) - return; - - if (self->sorted == NULL) - { - g_list_model_items_changed (G_LIST_MODEL (self), position, removed, added); - return; - } + guint n_items; - gtk_sort_list_model_remove_items (self, position, removed, &start, &end); - gtk_sort_list_model_add_items (self, position, added, &start2, &end2); - start = MIN (start, start2); - end = MIN (end, end2); + /* doesn't free() the array */ + sort_array_set_size (&self->items, 0); + gtk_sort_list_model_create_items (self); + gtk_sort_list_model_resort (self); - n_items = g_sequence_get_length (self->sorted) - start - end; - g_list_model_items_changed (G_LIST_MODEL (self), start, n_items - added + removed, n_items); + n_items = g_list_model_get_n_items (model); + g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items - added + removed, n_items); } static void @@ -296,47 +224,23 @@ gtk_sort_list_model_get_property (GObject *object, } } -static void -gtk_sort_list_model_clear_sequences (GtkSortListModel *self) -{ - g_clear_pointer (&self->unsorted, g_sequence_free); - g_clear_pointer (&self->sorted, g_sequence_free); -} - -static void -gtk_sort_list_model_create_sequences (GtkSortListModel *self) -{ - if (self->sorted) - return; - - if (self->sorter == NULL || - self->model == NULL || - gtk_sorter_get_order (self->sorter) == GTK_SORTER_ORDER_NONE) - return; - - self->sorted = g_sequence_new (gtk_sort_list_entry_free); - self->unsorted = g_sequence_new (NULL); - - gtk_sort_list_model_add_items (self, 0, g_list_model_get_n_items (self->model), NULL, NULL); -} - -static void gtk_sort_list_model_resort (GtkSortListModel *self); - static void gtk_sort_list_model_sorter_changed_cb (GtkSorter *sorter, int change, GtkSortListModel *self) { + guint n_items; + if (gtk_sorter_get_order (sorter) == GTK_SORTER_ORDER_NONE) - gtk_sort_list_model_clear_sequences (self); - else if (self->sorted == NULL) - { - guint n_items = g_list_model_get_n_items (self->model); - gtk_sort_list_model_create_sequences (self); - g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items); - } - else - gtk_sort_list_model_resort (self); + gtk_sort_list_model_clear_items (self); + else if (sort_array_is_empty (&self->items)) + gtk_sort_list_model_create_items (self); + + gtk_sort_list_model_resort (self); + + n_items = g_list_model_get_n_items (G_LIST_MODEL (self)); + if (n_items > 1) + g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items); } static void @@ -347,7 +251,7 @@ gtk_sort_list_model_clear_model (GtkSortListModel *self) g_signal_handlers_disconnect_by_func (self->model, gtk_sort_list_model_items_changed_cb, self); g_clear_object (&self->model); - gtk_sort_list_model_clear_sequences (self); + gtk_sort_list_model_clear_items (self); } static void @@ -358,7 +262,7 @@ gtk_sort_list_model_clear_sorter (GtkSortListModel *self) g_signal_handlers_disconnect_by_func (self->sorter, gtk_sort_list_model_sorter_changed_cb, self); g_clear_object (&self->sorter); - gtk_sort_list_model_clear_sequences (self); + gtk_sort_list_model_clear_items (self); } static void @@ -468,7 +372,8 @@ gtk_sort_list_model_set_model (GtkSortListModel *self, g_signal_connect (model, "items-changed", G_CALLBACK (gtk_sort_list_model_items_changed_cb), self); added = g_list_model_get_n_items (model); - gtk_sort_list_model_create_sequences (self); + gtk_sort_list_model_create_items (self); + gtk_sort_list_model_resort (self); } else added = 0; @@ -495,25 +400,6 @@ gtk_sort_list_model_get_model (GtkSortListModel *self) return self->model; } -static void -gtk_sort_list_model_resort (GtkSortListModel *self) -{ - guint n_items; - - g_return_if_fail (GTK_IS_SORT_LIST_MODEL (self)); - - if (self->sorted == NULL) - return; - - n_items = g_list_model_get_n_items (self->model); - if (n_items <= 1) - return; - - g_sequence_sort (self->sorted, _sort_func, self->sorter); - - g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items); -} - /** * gtk_sort_list_model_set_sorter: * @self: a #GtkSortListModel @@ -525,8 +411,6 @@ void gtk_sort_list_model_set_sorter (GtkSortListModel *self, GtkSorter *sorter) { - guint n_items; - g_return_if_fail (GTK_IS_SORT_LIST_MODEL (self)); g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter)); @@ -536,20 +420,22 @@ gtk_sort_list_model_set_sorter (GtkSortListModel *self, { self->sorter = g_object_ref (sorter); g_signal_connect (sorter, "changed", G_CALLBACK (gtk_sort_list_model_sorter_changed_cb), self); + gtk_sort_list_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self); + } + else + { + guint n_items = g_list_model_get_n_items (G_LIST_MODEL (self)); + if (n_items > 1) + g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items); } - gtk_sort_list_model_create_sequences (self); - - n_items = g_list_model_get_n_items (G_LIST_MODEL (self)); - if (n_items > 1) - g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items); g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]); } /** * gtk_sort_list_model_get_sorter: - * @self: a #GtkSortLisTModel + * @self: a #GtkSortListModel * * Gets the sorter that is used to sort @self. * -- 2.30.2